1. Field of the Invention
The present invention relates generally to data processing, and more particularly to a computer implemented method, system, and computer usable program code for post-register allocation selective instruction scheduling.
2. Description of the Related Art
The processing speed of processors has increased at a dramatic rate over the last few years. With this increase in processing speed, there is a demand for more effective computer systems. The need for faster and more sophisticated compilers and compiling frameworks is essential to enable overall performance gains. A compiler translates code written in higher level programming languages into code executable by the computer system. Many modern compilers are dynamic compilers or Just-in-Time (JIT) compilers. A dynamic compiler translates a whole segment of code into a native code that is executable by a processor in the computer system. Machine code is an example of native code. Because dynamic compilers compile code at runtime, a program that takes a long time to compile reduces overall performance of a computer system. In addition, the program appears to execute slower to the end-user creating user dissatisfaction with the computing system and program.
Various techniques are used to reduce the performance effects of dynamic compiling. For example, instruction scheduling is a compiler or run-time technique that rearranges the execution order and functional resource allocation of the instructions compiled from a computer program so the instructions execute in the fastest and most efficient order possible. While the rearranged stream of instructions is semantically equivalent to the original stream, the instruction scheduler arranges and overlaps the execution of instructions so as to reduce overall execution time.
Unfortunately, even simple instruction scheduling requires significant compilation time as well as increasing memory and execution overhead. More complex models for instruction scheduling may further sacrifice compilation time to attain better performance in the compiled code.
Instruction scheduling may also cause conflicts with register allocation. Register allocation involves assigning variables to a limited number of hardware registers during program execution because variables in registers may be accessed more quickly than unassigned variables. Because there are far more variables than registers, multiple variables assigned to the same register may have conflicts. The goal of register allocation is to assign variables that do not conflict so as to minimize the use of non-register memory.
For example, if instruction scheduling occurs before register allocation, the rescheduled code tends to increase register motion including register spills and spill instructions which may break instruction groupings and introduce pipeline stalls and other compilation delays. Register spills occur when there are insufficient registers available for all of the variables that need to be stored and memory instead of registers must be used.
If register allocation precedes instruction scheduling, the assignment of a limited number of real registers to an indefinite number of virtual registers may create false constraints on dependencies between instructions. These dependencies may limit instructions from being moved or organized effectively, especially in systems with relatively small register sets. As a result, effective instruction scheduling has been limited because of problems balancing register allocation and performance limitations.